17. 电话号码的字母组合

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

题目描述

Alt text

题目分析

这是一道比较简单的递归的问题，首先我们分析一下递归结构，如下图
Alt text

通过这样的一个图示也能够很清晰的看出其递归结构结构为：

其中w是从当前的字母列表中任选一个。

然后确定递归参数。
我们需要：

  • digits：
  • result：最终结果
  • step：前n-1次合成的字符串
  • n：第n次

最后确定递归边界：
递归边界为当n == len(n)，代表结束。

递归算法时间复杂度分析

假设每个数字对应3个字母，那么大致复杂度为$3^n$，等价于复杂度规模为$O(2^n)$。

总结

这种递归的方式实际上就是回溯法，回溯法实际上也是一种暴力解法，和多重循环一样。而这里由于不知道到底会有多少个数字，也就是长度是不定的，所以不能够用多重循环来求解。

回溯法非常重要，虽然他的效率不高，但是后续的很多算法都是在它的基础上演进的，比如使用各种剪枝的方法，比如动态规划等等。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    
    def __init__(self):
        self.word_dict = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }
        self.result = []
    
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return self.result
        
        self.combination(digits, 0, "")
        
        return self.result
        
    
    
    def combination(self, digits, n, step):
        
        if len(digits) == n:
            self.result.append(step)
            return
        
        words = self.word_dict[digits[n]]
        for w in words:
            if n ==0:
                step = w
            else:
                step += w
            self.combination(digits, n + 1, step)
            step = step[:-1]